LeetCode 402 、移掉 K 位数字

一、题目描述

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 移掉 K 位数字（ LeetCode 402 ）:https://leetcode-cn.com/problems/remove-k-digits/submissions/
class Solution {
    public String removeKdigits(String num, int k) {

        // 初始化栈，用来存储需要保留的数字
        Stack<Character> stack = new Stack<Character>();

        // 初始化字符串，用来保留最后的结果
        StringBuilder result = new StringBuilder();

        // 从左到右遍历字符串 num
        for(int i = 0 ; i < num.length();i++){
            
            // 获取此时遍历的字符
            char digit = num.charAt(i);
            
            // 如果此时
            // 1、栈不为空
            // 2、栈顶元素大于此时遍历的字符
            // 3、还没有删除足够多的数字，即 k > 0
            // 那么这个时候需要把栈顶元素弹出
            while(!stack.isEmpty() && stack.peek() > digit && k > 0){
                // 把栈顶元素弹出
                stack.pop();
                // 记录删除的个数减 1
                k--;
            }

            // 如果发现此时遍历的字符为 0 并且栈为空
            // 那么就不要把 0 放入到栈中，否则最终的结果会以 0 开头
            if(digit == '0' && stack.isEmpty()){
                continue;
            }

            // 把符合要求的字符放入到栈中
            stack.push(digit);
        }

        // 遍历完所有的字符后，如果发现还没有删除足够多的元素，那么需要继续删除
        // 什么数字会出现这种情况呢？
        // 比如数字为 123456789 ，删除的数字 k 为 1
        while(!stack.isEmpty() && k > 0){
            // 不断的弹出栈顶元素
            stack.pop();
            // 直到 k 为 0 位置
            k--;
        }

        // 操作完毕之后，如果发现栈为空，按上面逻辑我们会返回字符 "" ，
        // 但根据题目的示例 3，num = "10"， k = 2 时，从原数字移除所有的数字，剩余为空就是 0 
        // 需要返回 "0"
        if (stack.isEmpty()) return "0";

        // 如果栈中还有元素
        while(!stack.isEmpty()){
            // 那么从栈顶到栈底把字符添加到 result 上
            result.append(stack.peek());
            // 同时不断的弹出栈顶元素
            stack.pop();
        }

        // 由于 stack 中的栈底是数字的最高位，栈顶是最低位
        // 所以此时 result 保存的顺序是最低位到最高位
        // 需要执行一次翻转操作
        return result.reverse().toString();

    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 移掉 K 位数字（ LeetCode 402 ）:https://leetcode-cn.com/problems/remove-k-digits/submissions/
class Solution {
public:
    string removeKdigits(string num, int k) {
        // 初始化栈，用来存储需要保留的数字
        stack<char> s;

        // 初始化字符串，用来保留最后的结果
        string result = "" ;

        // 从左到右遍历字符串 num
        for(int i = 0 ; i < num.length();i++){
            
            // 获取此时遍历的字符
            int digit = num[i];
            
            // 如果此时
            // 1、栈不为空
            // 2、栈顶元素大于此时遍历的字符
            // 3、还没有删除足够多的数字，即 k > 0
            // 那么这个时候需要把栈顶元素弹出
            while(!s.empty() && s.top() > digit && k > 0){
                // 把栈顶元素弹出
                s.pop();
                // 记录删除的个数减 1
                k--;
            }

            // 如果发现此时遍历的字符为 0 并且栈为空
            // 那么就不要把 0 放入到栈中，否则最终的结果会以 0 开头
            if(digit == '0' && s.empty()){
                continue;
            }

            // 把符合要求的字符放入到栈中
            s.push(digit);
        }

        // 遍历完所有的字符后，如果发现还没有删除足够多的元素，那么需要继续删除
        // 什么数字会出现这种情况呢？
        // 比如数字为 123456789 ，删除的数字 k 为 1
        while(!s.empty() && k > 0){
            // 不断的弹出栈顶元素
            s.pop();
            // 直到 k 为 0 位置
            k--;
        }

        // 操作完毕之后，如果发现栈为空，按上面逻辑我们会返回字符 "" ，
        // 但根据题目的示例 3，num = "10"， k = 2 时，从原数字移除所有的数字，剩余为空就是 0 
        // 需要返回 "0"
        if (s.empty()) return "0";

        // 如果栈中还有元素
        while(!s.empty()){
            // 那么从栈顶到栈底把字符添加到 result 上
            result += s.top();
            // 同时不断的弹出栈顶元素
            s.pop();
        }

        // 由于 s 中的栈底是数字的最高位，栈顶是最低位
        // 所以此时 result 保存的顺序是最低位到最高位
        // 需要执行一次翻转操作
        reverse(result.begin(), result.end());

        return result;
    }
};

3、Python 代码

登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 移掉 K 位数字（ LeetCode 402 ）:https://leetcode-cn.com/problems/remove-k-digits/submissions/
class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # 初始化栈，用来存储需要保留的数字
        stack = []
        
        # 从左到右遍历字符串 num
        for digit in num:
            
            # 如果此时
            # 1、栈不为空
            # 2、栈顶元素大于此时遍历的字符
            # 3、还没有删除足够多的数字，即 k > 0
            # 那么这个时候需要把栈顶元素弹出
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1

            # 把符合要求的字符放入到栈中
            stack.append(digit)

        return ''.join(stack[:len(stack) - k]).lstrip('0') or "0"